class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums)
    {
        int ret = 1;
        int i = 0, j = 0;
        int n = nums.size();
        while (j < n)
        {
            j = i + 1;
            while (j < n && nums[j] > nums[j - 1]) j++;
            ret = max(ret, j - i);
            i = j;
        }
        return ret;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > ret.back()) ret.push_back(nums[i]);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (nums[i] > ret[mid]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }
        return ret.size();
    }
};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > ret.back()) ret.push_back(nums[i]);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (nums[i] > ret[mid]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }
        return ret.size();
    }
};
class Solution {
public:
    bool increasingTriplet(vector<int>& nums)
    {
        int n = nums.size();
        int a = nums[0];
        int b = INT_MAX;
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > b) return true;
            else
            {
                if (nums[i] > a) b = nums[i];
                else a = nums[i];
            }
        }
        return false;
    }
};
class Solution {
public:
    int longestPalindrome(string s)
    {
        unordered_map<char, int> hash;
        for (auto ch : s) hash[ch]++;
        int ret = 0;
        for (auto [x, y] : hash)
        {
            ret += y / 2 * 2;
        }
        if (ret < s.size()) ret++;
        return ret;
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int ret = 0;
        int n = prices.size();

        for (int i = 0; i < n - 1; i++)
        {
            if (prices[i + 1] > prices[i]) ret += prices[i + 1] - prices[i];
        }
        return ret;
    }
};